#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define random(x) (rand()%x)

/*Limit the maximum length of the array for convenience*/
#define ARR_LEN 500

#define MAX_NUM 150

void exchange_seq_val(int[] , int, int);

void quick_sort(int[] , int, int);

void buildiArray(unsigned *arr, size_t len)
{
    /*printf(
            "%ld %ld %d %d %d %d \n",
            (long)INT_MAX,
            (long)UINT_MAX,
            INT_MAX,
            UINT_MAX,
            SHRT_MAX,
            USHRT_MAX

            );
    */

    for (int i = 0; i<len; ++i) {
        arr[i] = random(MAX_NUM);
    }
}




int main(void){
    int l;

    do {

        printf("请输入待排序数组的长度! (最大长度%u): ", ARR_LEN);
        scanf("%u", &l);

    } while (l > ARR_LEN || l<=0);

    unsigned seq[ARR_LEN] = {0};

    buildiArray(seq, l);

    printf("-------- before sort --------\n");

    for (int i=0; i<l; i++) {
        printf("%u ", seq[i]);
    }

    printf("\n\n");

    printf("-------- after sort ---------\n");

    quick_sort(seq, 0, l-1);

    for (int i=0; i<l; i++) {
        printf("%u ", seq[i]);
    }
    putchar('\n');

    return 0;
}

void quick_sort(int *seq, int start, int end)
{

    if (start >= end) {
        return;
    }

    int base = seq[start];

    int s = start + 1;

    int bi = start;

    for (; s <= end; ++s) {
        if (base >= seq[s]) exchange_seq_val(seq, s, ++bi);
    }

    exchange_seq_val(seq, start, bi);

    quick_sort(seq, start, bi-1);
    quick_sort(seq, bi+1, end);
}

/*Swap values in two places in an array */
void exchange_seq_val(int *seq, int f, int s)
{

    if (f != s) {
        seq[f] = seq[f] ^ seq[s];
        seq[s] = seq[f] ^ seq[s];
        seq[f] = seq[f] ^ seq[s];
    }
}

